// 真题描述：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL


const reverseList = function (head) {
    // 初始化前驱结点 为null
    let pre = null
    let cur = head
    while(cur !== null) {
        let next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
}


function ListNode (val) {
    this.val = val || ''
    this.next = null
}
// 链表局部反转
const reversebetween = function (head, m, n) {
    // 定义pre, cur, 用leftHead来承接整个区间的前驱结点
    let pre, cur, leftHead
    // 头节点的前驱结点
    let dummy = new ListNode()
    dummy.next = head
    // p 是一个游标，用于遍历，最初指向dummy
    let p = dummy
    // p往前走m-1 步，走到整个区间的前驱结点处
    for(let i = 0; i<m-1; i++) {
        p = p.next
    }
    // 缓存这个前驱结点在leftHead里
    leftHead = p
    let start = leftHead.next // start 是反转区间的第一个结点
    // pre 指向start
    pre = start
    // cur 指向start的下一个结点
    cur = pre.next

    // 进行反转操作
    for(let i = m; i< n; i++) {
        let next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    // leftHead 的后继结点此时为反转后的区间的第一个结点
    leftHead.next = pre
    // 将区间内反转后的最后一个结点next 指向反转后的最后一个结点
    start.next = cur

    return dummy.next
}
